package problem437;

import java.util.HashMap;
import java.util.Map;

//437.路劲总和3
//https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    int ret = 0;
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
        map.put(0l,1);
        f(root, targetSum, 0, map);
        return ret;
    }
    public void f(TreeNode root, int targetSum, long sum, Map<Long, Integer> map) {
        if(root == null) return;

        sum += root.val;
        ret += map.getOrDefault(sum - targetSum, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);

        f(root.left, targetSum, sum, map);
        f(root.right, targetSum, sum, map);
        //回溯
        map.put(sum, map.getOrDefault(sum, 0) - 1);
    }
}